package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 这种题不能秒杀实在是……
 * */
public class _46_permute {
    
    class totally_wrong {
        int[] nums;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            this.nums = nums;
            backtrack(0);
            return res;
        }
        // 希望下面这个会帮到我
        // 1 2 3，1 3 2，2 1 3，2 3 1, 3 1 2， 3 2 1
        void backtrack(int idx) {
            if (idx == nums.length) {
                res.add(new ArrayList<>(each));
                return;
            }
            // 都基于交换了，你还 add 啥呢？
            each.add(nums[idx]);
            for (int i = idx; i < nums.length; i++) {
                swap(nums, idx, i);
                backtrack(idx + 1);
                swap(nums, idx, i);
            }
            each.remove(each.size() - 1);
        }
    
        void swap(int[] nums, int i, int j) {
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
    }
    
    class recite {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            for (int num : nums) {
                each.add(num);
            }
            backtrack(0, nums.length);
            return res;
        }
        void backtrack(int idx, int n) {
            if (idx == n) {
                res.add(new ArrayList<>(each));
            } else {
                for (int i = idx; i < n; i++) {
                    Collections.swap(each, idx, i);
                    backtrack(idx + 1, n); // 有的人以为，这个循环每次都是 idx + 1 是不是错了，其实不然
                    Collections.swap(each, idx, i);
                }
            }
        }
    }
}
